package com.sy.algorithm;

/**
 * 5. 最长回文子串
 *
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 *  
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @Author zb
 * @Date 2022/3/11 20:11
 */
public class Algorithm005 {

    public static void main(String[] args){

        Solution solution = new Solution();
        String s = "ccc";

        String result = solution.longestPalindrome(s);

        System.out.println(result);
    }

    private static class Solution {
        public String longestPalindrome(String s) {
            //最简单的实现 for（for0-i）
            String maxStr = "";
            for(int i = 0; i < s.length(); i++){
                char iChar = s.charAt(i);
                String curMaxStr = iChar + "";
                //对称轴在i上
                for(int j = i - 1 ; j >= 0 && 2*i - j < s.length(); j--){
                    int k = 2*i - j;
                    char jChar = s.charAt(j);
                    char kChar = s.charAt(k);
                    if(jChar == kChar){
                        String temp = s.substring(j,k+1);
                        if(temp.length() > curMaxStr.length()){
                            curMaxStr = temp;
                        }
                    }else{
                        break;
                    }
                }

                //对称轴在i与i+1 之间
                for(int j = i; j >=0 && 2*i - j + 1 < s.length(); j--){
                    int k = 2*i - j + 1;
                    char jChar = s.charAt(j);
                    char kChar = s.charAt(k);
                    if(jChar == kChar){
                        String temp = s.substring(j,k+1);
                        if(temp.length() > curMaxStr.length()){
                            curMaxStr = temp;
                        }
                    }else{
                        break;
                    }
                }
                if(curMaxStr.length()>maxStr.length()){
                    maxStr = curMaxStr;
                }
            }
            return maxStr;
        }
    }

}
